/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
 public:
  // 遍历顺序由后到前，处理顺序先进后出，适合用栈的结构
  // 创建了一个新的链表
  ListNode* plusOne(ListNode* head) {
    stack<int> st;
    while (head) {
      st.push(head->val);
      head = head->next;
    }
    ListNode* dummy = new ListNode(0);
    int adder = 1, carry = 0, digit, sum;
    while (!st.empty() || adder != 0 || carry > 0) {  // ******
      int digit = 0;                                  // *****
      if (!st.empty()) {
        digit = st.top();
        st.pop();
      }
      sum = digit + adder + carry;
      carry = sum >= 10 ? 1 : 0;
      sum = sum >= 10 ? sum - 10 : sum;
      ListNode* cur = new ListNode(sum);
      cur->next = dummy->next;
      dummy->next = cur;
      adder = 0;
    }
    return dummy->next;
  }

  // 递归
  // 因为由边界处理，所以无法写在一个函数里
  ListNode* plusOne(ListNode* head) {
    int carry = 0;
    Myplus(head, carry);
    return head->val == 0 ? new ListNode(1, head) : head;
  }
  void Myplus(ListNode* head, int& carry) {
    if (head == nullptr) return;
    Myplus(head->next, carry);
    if (head->next == nullptr || carry) {
      ++head->val;
      if (head->val == 10) {
        carry = 1;
        head->val = 0;
      } else {
        carry = 0;
      }
    }
  }
};